package com.sheng.leetcode.year2022.month06.day20;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/06/20
 *
 * 715. Range 模块
 *
 * Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
 * 半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
 * 实现 RangeModule 类:
 *
 * RangeModule() 初始化数据结构的对象。
 * void addRange(int left, int right) 添加 半开区间 [left, right)，跟踪该区间中的每个实数。
 * 添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
 * boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，
 * 才返回 true ，否则返回 false 。
 * void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
 *  
 *
 * 示例 1：
 *
 * 输入
 * ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
 * [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
 * 输出
 * [null, null, null, true, false, true]
 *
 * 解释
 * RangeModule rangeModule = new RangeModule();
 * rangeModule.addRange(10, 20);
 * rangeModule.removeRange(14, 16);
 * rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪）
 * rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
 * rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）
 *
 * 提示：
 *
 * 1 <= left < right <= 109
 * 在单个测试用例中，对 addRange 、  queryRange 和 removeRange 的调用总数不超过 104 次
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/range-module
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0715 {

    @Test
    public void test01(){
//        RangeModule rangeModule = new RangeModule();
//        rangeModule.addRange(10, 20);
//        rangeModule.removeRange(14, 16);
//        System.out.println(rangeModule.queryRange(10, 14));
//        System.out.println(rangeModule.queryRange(13, 15));
//        System.out.println(rangeModule.queryRange(16, 17));

//        RangeModule rangeModule = new RangeModule();
//        rangeModule.addRange(10, 180);
//        rangeModule.addRange(150, 200);
//        rangeModule.addRange(250, 500);
//        System.out.println(rangeModule.queryRange(50, 100));
//        System.out.println(rangeModule.queryRange(180, 300));
//        System.out.println(rangeModule.queryRange(600, 1000));
//        rangeModule.removeRange(50, 150);
//        System.out.println(rangeModule.queryRange(50, 100));

//        RangeModule rangeModule = new RangeModule();
//        rangeModule.addRange(6, 8);
//        rangeModule.removeRange(7, 8);
//        rangeModule.removeRange(8, 9);
//        rangeModule.addRange(8, 9);
//        rangeModule.removeRange(1, 3);
//        rangeModule.addRange(1, 8);
//        System.out.println(rangeModule.queryRange(2, 4));
//        System.out.println(rangeModule.queryRange(2, 9));
//        System.out.println(rangeModule.queryRange(4, 6));

        RangeModule rangeModule = new RangeModule();
        rangeModule.addRange(10, 20);
        rangeModule.addRange(20, 25);
        rangeModule.addRange(26, 30);
        rangeModule.removeRange(14, 16);
        System.out.println(rangeModule.queryRange(20, 21));
        System.out.println(rangeModule.queryRange(25, 26));
    }

}
class RangeModule {

    TreeSet<Range> rangeSet;

    public RangeModule() {
        rangeSet = new TreeSet<>();
    }

    public void addRange(int left, int right) {
        //TreeSet.tailSet(E fromElement) 方法用于返回一组大于或等于指定元素的元素
        Iterator<Range> iterator = rangeSet.tailSet(new Range(0, left)).iterator();
        while (iterator.hasNext()) {
            Range next = iterator.next();
            //如果新增的右边界位于当前循环的左边界左边，意味着没有重合，新增的区域位于当前循环的区域的左边
            if (next.getLeft() > right) {
                break;
            }
            //存在重合部分，即将两个边界左边界最小的值作为新的左边界，右边界最大的值作为新的右边界
            left = Math.min(left, next.getLeft());
            right = Math.max(right, next.getRight());
            //然后去除重合了的当前循环
            iterator.remove();
        }
        //将重新计算过后的新区域插入set集合中
        rangeSet.add(new Range(left, right));
    }

    public boolean queryRange(int left, int right) {
        //TreeSet.higher() 方法用于从集合中返回指定元素中最接近的最大元素，如果没有，则返回null
        Range higher = rangeSet.higher(new Range(0, left));
        return (higher != null && higher.getLeft() <= left && higher.getRight()>= right);
    }

    public void removeRange(int left, int right) {
        Iterator<Range> iterator = rangeSet.tailSet(new Range(0, left)).iterator();
        List<Range> ranges = new ArrayList<>();
        while (iterator.hasNext()) {
            Range next = iterator.next();
            //要去除的区域整体位于当前循环区域的左边，没有重合
            if (next.getLeft() > right) {
                break;
            }
            //要去除的区域和当前循环区域的右边部分有重合
            if (next.getLeft() < left) {
                ranges.add(new Range(next.getLeft(), left));
            }
            //要去除的区域和当前循环区域的左边部分有重合
            if (next.getRight() > right) {
                ranges.add(new Range(right, next.getRight()));
            }
            //去除和要删除区域有重合的循环区域
            iterator.remove();
        }
        rangeSet.addAll(ranges);
    }
}

class Range implements Comparable<Range>{

    private int left;

    private int right;

    public int getLeft() {
        return left;
    }

    public void setLeft(int left) {
        this.left = left;
    }

    public int getRight() {
        return right;
    }

    public void setRight(int right) {
        this.right = right;
    }

    public Range() {
    }

    public Range(int left, int right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public int compareTo(Range range) {
        if (this.right == range.right) {
            return this.left - range.left;
        }
        return this.right - range.right;
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */
